<p>Using regular expressions is security-sensitive. It has led in the past to the following vulnerabilities:</p>
<ul>
  <li> <a href="http://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2017-16021">CVE-2017-16021</a> </li>
  <li> <a href="http://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2018-13863">CVE-2018-13863</a> </li>
</ul>
<p>Evaluating regular expressions against input strings is potentially an extremely CPU-intensive task. Specially crafted regular expressions such as
<code>(a+)+s</code> will take several seconds to evaluate the input string <code>aaaaaaaaaaaaaaaaaaaaaaaaaaaaabs</code>. The problem is that with
every additional <code>a</code> character added to the input, the time required to evaluate the regex doubles. However, the equivalent regular
expression, <code>a+s</code> (without grouping) is efficiently evaluated in milliseconds and scales linearly with the input size.</p>
<p>Evaluating such regular expressions opens the door to <a
href="https://www.owasp.org/index.php/Regular_expression_Denial_of_Service_-_ReDoS">Regular expression Denial of Service (ReDoS)</a> attacks. In the
context of a web application, attackers can force the web server to spend all of its resources evaluating regular expressions thereby making the
service inaccessible to genuine users.</p>
<p>This rule flags any execution of a hardcoded regular expression which has at least 3 characters and at least two instances of any of the following
characters: <code>*+{</code>.</p>
<p>Example: <code>(a+)*</code></p>
<h2>Ask Yourself Whether</h2>
<ul>
  <li> the executed regular expression is sensitive and a user can provide a string which will be analyzed by this regular expression. </li>
  <li> your regular expression engine performance decrease with specially crafted inputs and regular expressions. </li>
</ul>
<p>You may be at risk if you answered yes to any of those questions.</p>
<h2>Recommended Secure Coding Practices</h2>
<p>Check whether your regular expression engine (the algorithm executing your regular expression) has any known vulnerabilities. Search for
vulnerability reports mentioning the one engine you're are using.</p>
<p>Use if possible a library which is not vulnerable to Redos Attacks such as <a href="https://github.com/google/re2">Google Re2</a>.</p>
<p>Remember also that a ReDos attack is possible if a user-provided regular expression is executed. This rule won't detect this kind of injection.</p>
<h2>Sensitive Code Example</h2>
<pre>
import java.util.regex.Pattern;

class BasePattern {
  String regex = "(a+)+b"; // a regular expression
  String input; // a user input

  void foo(CharSequence htmlString) {
    input.matches(regex);  // Sensitive
    Pattern.compile(regex);  // Sensitive
    Pattern.compile(regex, Pattern.CASE_INSENSITIVE);  // Sensitive

    String replacement = "test";
    input.replaceAll(regex, replacement);  // Sensitive
    input.replaceFirst(regex, replacement);  // Sensitive

    if (!Pattern.matches(".*&lt;script&gt;(a+)+b", htmlString)) { // Sensitive
    }
  }
}
</pre>
<p>This also applies for bean validation, where regexp can be specified:</p>
<pre>
import java.io.Serializable;
import javax.validation.constraints.Pattern;
import javax.validation.constraints.Email;
import org.hibernate.validator.constraints.URL;

class BeansRegex implements Serializable {
  @Pattern(regexp=".+@(a+)+b")  // Sensitive
  private String email;

  @Email(regexp=".+@(a+)+b")  // Sensitive
  private String email2;

  @URL(regexp="(a+)+b.com") // Sensitive
  private String url;
  // ...
}
</pre>
<h2>Exceptions</h2>
<p>Calls to <code>String.split(regex)</code> and <code>String.split(regex, limit)</code> will not raise an exception despite their use of a regular
expression. These methods are used most of the time to split on simple regular expressions which don't create any vulnerabilities.</p>
<p>Some corner-case regular expressions will not raise an issue even though they might be vulnerable. For example: <code>(a|aa)+</code>,
<code>(a|a?)+</code>.</p>
<p>It is a good idea to test your regular expression if it has the same pattern on both side of a "<code>|</code>".</p>
<h2>See</h2>
<ul>
  <li> <a href="https://www.owasp.org/index.php/Top_10-2017_A1-Injection">OWASP Top 10 2017 Category A1</a> - Injection </li>
  <li> <a href="https://www.owasp.org/index.php/Regular_expression_Denial_of_Service_-_ReDoS">MITRE, CWE-624</a> - Executable Regular Expression Error
  </li>
  <li> OWASP Regular expression Denial of Service - ReDoS </li>
</ul>

